package com.lihepeng.leecode.tree;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

/**
 * 后续递归
 * 左节点 -> 右节点 -> 根节点
 */
public class PostOrderTravel {
    /**
     * 使用递归的方案进行遍历
     *
     * @param treeNode
     * @return
     */
    public List<Integer> postOrderTravel(TreeNode treeNode) {
        List<Integer> res = new ArrayList<>();
        if (treeNode == null) {
            return res;
        }
        res.addAll(postOrderTravel(treeNode.left));
        res.addAll(postOrderTravel(treeNode.right));
        res.add(treeNode.val);
        return res;
    }

    /**
     * 借助于栈结构完成遍历
     *
     * @param treeNode
     * @return
     */
    public List<Integer> postOrderTravel01(TreeNode treeNode) {
        List<Integer> res = new ArrayList<>();
        if (treeNode == null) {
            return null;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(treeNode);
        res.add(treeNode.val);
        TreeNode currNode = treeNode.right;
        while (!stack.isEmpty() || currNode != null) {
            while (currNode != null) {
                stack.push(currNode);
                res.add(currNode.val);
                currNode = currNode.right;
            }
            currNode = stack.pop();
            currNode = currNode.left;
        }
        Collections.reverse(res);
        return res;
    }

    @Test
    public void runTest() {
        TreeNode head = new TreeNode(0);
        TreeNode n1 = new TreeNode(1);
        TreeNode n2 = new TreeNode(2);
        TreeNode n3 = new TreeNode(3);
        TreeNode n4 = new TreeNode(4);
        TreeNode n5 = new TreeNode(5);
        head.left = n1;
        head.right = n2;
        n1.left = n3;
        n1.right = n4;
        n2.left = n5;
        List<Integer> list = postOrderTravel01(head);
        System.out.println(list);
    }
}
